home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / basic / pbc_bas.exe / SORTST.BAS < prev    next >
Encoding:
BASIC Source File  |  1993-01-01  |  2.3 KB  |  77 lines
  1. '   +----------------------------------------------------------------------+
  2. '   |                                                                      |
  3. '   |        PBClone  Copyright (c) 1990-1993  Thomas G. Hanlin III        |
  4. '   |                                                                      |
  5. '   +----------------------------------------------------------------------+
  6.  
  7. ' QuickSort derived from "partition sort" algorithm given in
  8. ' "Algorithms & Data Structures" by Niklaus Wirth, 1986
  9.  
  10.    TYPE Partition
  11.       Lft AS INTEGER
  12.       Rht AS INTEGER
  13.    END TYPE
  14.  
  15. SUB SortSt (Array() AS STRING, Elements%, CapsCount%)
  16.    DIM x AS STRING
  17.    DIM SortStack(1 TO 16) AS Partition
  18.    S% = 1
  19.    SortStack(1).Lft = 1
  20.    SortStack(1).Rht = Elements%
  21.    DO
  22.       L% = SortStack(S%).Lft
  23.       R% = SortStack(S%).Rht
  24.       S% = S% - 1
  25.       DO
  26.          i% = L%
  27.          j% = R%
  28.          IF CapsCount% THEN
  29.             x = Array((L% + R%) \ 2)
  30.             DO
  31.                WHILE Array(i%) < x
  32.                   i% = i% + 1
  33.                WEND
  34.                WHILE x < Array(j%)
  35.                   j% = j% - 1
  36.                WEND
  37.                IF i% <= j% THEN
  38.                   SWAP Array(i%), Array(j%)
  39.                   i% = i% + 1
  40.                   j% = j% - 1
  41.                END IF
  42.             LOOP UNTIL i% > j%
  43.          ELSE
  44.             x = UCASE$(Array((L% + R%) \ 2))
  45.             DO
  46.                WHILE UCASE$(Array(i%)) < x
  47.                   i% = i% + 1
  48.                WEND
  49.                WHILE x < UCASE$(Array(j%))
  50.                   j% = j% - 1
  51.                WEND
  52.                IF i% <= j% THEN
  53.                   SWAP Array(i%), Array(j%)
  54.                   i% = i% + 1
  55.                   j% = j% - 1
  56.                END IF
  57.             LOOP UNTIL i% > j%
  58.          END IF
  59.          IF j% - L% < R% - i% THEN
  60.             IF i% < R% THEN
  61.                S% = S% + 1
  62.                SortStack(S%).Lft = i%
  63.                SortStack(S%).Rht = R%
  64.             END IF
  65.             R% = j%
  66.          ELSE
  67.             IF L% < j% THEN
  68.                S% = S% + 1
  69.                SortStack(S%).Lft = L%
  70.                SortStack(S%).Rht = j%
  71.             END IF
  72.             L% = i%
  73.          END IF
  74.       LOOP UNTIL L% >= R%
  75.    LOOP WHILE S%
  76. END SUB
  77.